package com.lwt.codetop.stack;

// 20. 有效的括号

import java.util.HashMap;
import java.util.Stack;

/**
 * 思路：括号匹配问题，栈实现
 *      遇到左括号则入栈；
 *      遇到右括号：当栈空说明不匹配、当括号不匹配说明不匹配。反之，匹配，左括号弹出栈
 *      最后判断栈是否为空，为空则是合法括号序列
 */
public class ValidParentheses {
    public static void main(String[] args) {
        // 构建测试用例
        String s = "()[]{}";
        // 括号匹配
        boolean res = isValid(s);
        System.out.println(res);
    }

    /**
     * 用栈实现括号序号是否匹配判断
     * @param s
     * @return
     */
    private static boolean isValid(String s){
        char[] charArray = s.toCharArray();
        Stack<Character> stk = new Stack<>();

        HashMap<Character, Character> mp = new HashMap<>();
        mp.put(')', '(');
        mp.put(']', '[');
        mp.put('}', '{');

        for (char x : charArray) {
            if(x == '(' || x == '[' || x == '{') stk.add(x);
            else {
                if(stk.isEmpty() || stk.peek() != mp.get(x)) return false;
                stk.pop();
            }
        }
        return stk.isEmpty();
    }
}
